Rows vs Columns for Linear Systems of Equations - Randomized Kaczmarz or Coordinate Descent?

摘要

This paper is about randomized iterative algorithms for solving a linearsystem of equations $X \beta = y$ in different settings. Recent interest in thetopic was reignited when Strohmer and Vershynin (2009) proved the linearconvergence rate of a Randomized Kaczmarz (RK) algorithm that works on the rowsof $X$ (data points). Following that, Leventhal and Lewis (2010) proved thelinear convergence of a Randomized Coordinate Descent (RCD) algorithm thatworks on the columns of $X$ (features). The aim of this paper is to simplifyour understanding of these two algorithms, establish the direct relationshipsbetween them (though RK is often compared to Stochastic Gradient Descent), andexamine the algorithmic commonalities or tradeoffs involved with working onrows or columns. We also discuss Kernel Ridge Regression and present aKaczmarz-style algorithm that works on data points and having the advantage ofsolving the problem without ever storing or forming the Gram matrix, one of therecognized problems encountered when scaling kernelized methods.